package alogrithm.solution;

/*
 * 30.在从1到n的正数中1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
分析：这是一道广为流传的google面试题。
 */
public class P30 {
	public static int getOnesNumSmallerThanN(int n)
	{
		String str=((Integer)n).toString();
		int l=str.length()-1,sum=0;
		for(int i=0;i<=l;i++)
		{
			if(str.charAt(i)>='2')sum+=Math.pow(10, l-i);
			else if(str.charAt(i)=='1')
			{
				int remainder=0;
				if(i==l)
					remainder=1;
				else
				{
					String tmp=str.substring(i+1);
					remainder=Integer.parseInt(tmp)+1;
				}
				sum+=remainder;
			}
			if(!str.substring(0, i).equals(""))
			{
				sum+=Math.pow(10, l-i)*Integer.parseInt(str.substring(0, i));
			}
		}
		return sum;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(getOnesNumSmallerThanN(21));

	}

}
